package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] keys = new int[]{38, 38, 97, 75, 61, 19, 26, 49};
        System.out.print("关键字序列：");
        System.out.println(Arrays.toString(keys));
        quickSort.quickSort(keys);
    }

    //9.2.2   快速排序
    public void quickSort(int[] keys) {
        System.out.println("快速排序（升序）");
        quickSort(keys, 0, keys.length - 1);
    }

    //对存于keys数组begin～end之间的子序列进行一趟快速排序，递归算法
    private void quickSort(int[] keys, int begin, int end) {
        //序列有效
        if (begin >= 0 && begin < keys.length
                && end >= 0 && end < keys.length
                && begin < end) {
            int i = begin, j = end;                            //i、j下标分别从子序列的前后两端开始
            int vot = keys[i];                               //子序列第一个值作为基准值
            while (i != j) {
                while (i < j && keys[j] >= vot)                //（升序）从后向前寻找较小值，不移动与基准值相等元素
                    j--;
                if (i < j)
                    keys[i++] = keys[j];                     //子序列后端较小元素向前移动
                while (i < j && keys[i] <= vot)                //（升序）从前向后寻找较大值，不移动与基准值相等元素
                    i++;
                if (i < j)
                    keys[j--] = keys[i];                     //子序列前端较大元素向后移动
            }
            keys[i] = vot;                                   //基准值到达最终位置
            System.out.print("下标" + begin + "～" + end + "， vot=" + vot + "，  ");
            System.out.println(Arrays.toString(keys));
            quickSort(keys, begin, j - 1);                   //前端子序列再排序，递归调用
            quickSort(keys, i + 1, end);                     //后端子序列再排序，递归调用
        }
    }
}
